{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K Divisible Elements Subarrays"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #trie #array #hash-table #enumeration #hash-function #rolling-hash"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字典树 #数组 #哈希表 #枚举 #哈希函数 #滚动哈希"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countDistinct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #含最多 K 个可整除元素的子数组"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数数组 <code>nums</code> 和两个整数 <code>k</code> 和 <code>p</code> ，找出并返回满足要求的不同的子数组数，要求子数组中最多 <code>k</code> 个可被 <code>p</code> 整除的元素。</p>\n",
    "\n",
    "<p>如果满足下述条件之一，则认为数组 <code>nums1</code> 和 <code>nums2</code> 是 <strong>不同</strong> 数组：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>两数组长度 <strong>不同</strong> ，或者</li>\n",
    "\t<li>存在 <strong>至少 </strong>一个下标 <code>i</code> 满足 <code>nums1[i] != nums2[i]</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p><strong>子数组</strong> 定义为：数组中的连续元素组成的一个 <strong>非空</strong> 序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [<em><strong>2</strong></em>,3,3,<em><strong>2</strong></em>,<em><strong>2</strong></em>], k = 2, p = 2\n",
    "<strong>输出：</strong>11\n",
    "<strong>解释：</strong>\n",
    "位于下标 0、3 和 4 的元素都可以被 p = 2 整除。\n",
    "共计 11 个不同子数组都满足最多含 k = 2 个可以被 2 整除的元素：\n",
    "[2]、[2,3]、[2,3,3]、[2,3,3,2]、[3]、[3,3]、[3,3,2]、[3,3,2,2]、[3,2]、[3,2,2] 和 [2,2] 。\n",
    "注意，尽管子数组 [2] 和 [3] 在 nums 中出现不止一次，但统计时只计数一次。\n",
    "子数组 [2,3,3,2,2] 不满足条件，因为其中有 3 个元素可以被 2 整除。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3,4], k = 4, p = 1\n",
    "<strong>输出：</strong>10\n",
    "<strong>解释：</strong>\n",
    "nums 中的所有元素都可以被 p = 1 整除。\n",
    "此外，nums 中的每个子数组都满足最多 4 个元素可以被 1 整除。\n",
    "因为所有子数组互不相同，因此满足所有限制条件的子数组总数为 10 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= nums[i], p &lt;= 200</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= nums.length</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>进阶：</strong></p>\n",
    "\n",
    "<p>你可以设计并实现时间复杂度为 <code>O(n<sup>2</sup>)</code> 的算法解决此问题吗？</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-divisible-elements-subarrays](https://leetcode.cn/problems/k-divisible-elements-subarrays/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-divisible-elements-subarrays](https://leetcode.cn/problems/k-divisible-elements-subarrays/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,3,3,2,2]\\n2\\n2', '[1,2,3,4]\\n4\\n1']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        v = [0] * n\n",
    "        count = 0\n",
    "        i1 = -1\n",
    "        for i2 in range(n):\n",
    "            if nums[i2] % p == 0:\n",
    "                count += 1\n",
    "            if count > k:\n",
    "                i1 += 1\n",
    "                while nums[i1] % p != 0:\n",
    "                    i1 += 1\n",
    "                count -= 1\n",
    "            v[i2] = i2 - i1\n",
    "        res = v[0]\n",
    "        a = []\n",
    "        for i in range(1, n):\n",
    "            b = [1 if nums[i] == nums[0] else 0]\n",
    "            for j in range(1, i):\n",
    "                b.append(a[j-1] + 1 if nums[i] == nums[j] else 0)\n",
    "            res += max(v[i] - max(b), 0)\n",
    "            a = b\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = 0\n",
    "\n",
    "        power = []\n",
    "        t = 1\n",
    "        for i in range(n):\n",
    "            power.append(t)\n",
    "            t *= 211\n",
    "        \n",
    "        for d in range(1, n + 1):\n",
    "            s = set()\n",
    "            count = 0\n",
    "            hash = 0\n",
    "            for i in range(n):\n",
    "                hash = hash * 211 + nums[i]\n",
    "                if nums[i] % p == 0:\n",
    "                    count += 1\n",
    "                if i < d - 1:\n",
    "                    continue\n",
    "                if i >= d:\n",
    "                    count -= (1 if nums[i-d] % p == 0 else 0)\n",
    "                    hash -= (nums[i-d] * power[d])\n",
    "                if count <= k:\n",
    "                    if hash in s:\n",
    "                        continue\n",
    "                    s.add(hash)\n",
    "                    res += 1\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: list[int], k: int, p: int) -> int:\n",
    "        specIndexs = []\n",
    "        n=len(nums)\n",
    "        result = 0\n",
    "        for i in range(0,n):\n",
    "            if nums[i]%p==0:\n",
    "                specIndexs.append(i)\n",
    "        for j in range(1,n+1):\n",
    "            jResults = []\n",
    "            for i in range(0,n-j+1):\n",
    "                between = 0\n",
    "                for l in range(0,len(specIndexs)):\n",
    "                    if i<=specIndexs[l]<=i+j-1:\n",
    "                        between+=1\n",
    "                    elif specIndexs[l]>i+j-1:\n",
    "                        break\n",
    "                if between>k:\n",
    "                    continue\n",
    "                checkResult = nums[i:i+j]\n",
    "                check = True\n",
    "                for jResult in jResults:\n",
    "                    if not check:\n",
    "                        break\n",
    "                    for index in range(0,j):\n",
    "                        if jResult[index]!=checkResult[index]:\n",
    "                            break\n",
    "                    else:\n",
    "                        check =False\n",
    "                if check:\n",
    "                    jResults.append(checkResult)\n",
    "            result += len(jResults)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        cnt = 0\n",
    "        pre = -1\n",
    "        ret = 0\n",
    "        q = []\n",
    "        qs = []\n",
    "        def cmp(a, b):\n",
    "            l1, r1 = a\n",
    "            l2, r2 = b\n",
    "            if r1 - l1 < r2 - l2:\n",
    "                return -1\n",
    "            if r1 - l1 > r2 - l2:\n",
    "                return 1\n",
    "            while l1 <= r1:\n",
    "                if nums[l1] < nums[l2]:\n",
    "                    return -1\n",
    "                if nums[l1] > nums[l2]:\n",
    "                    return 1\n",
    "                l1 += 1\n",
    "                l2 += 1\n",
    "            return -1 if r1 < r2 else 1\n",
    "        \n",
    "        for i in range(n):\n",
    "            if nums[i] % p == 0:\n",
    "                cnt += 1\n",
    "                q.append(i)\n",
    "                if cnt > k:\n",
    "                    cnt -= 1\n",
    "                    pre = q.pop(0)\n",
    "            ret += i - pre\n",
    "            for j in range(pre + 1, i + 1):\n",
    "                qs.append((j, i))\n",
    "            # print(pre, i, q)\n",
    "        # print(qs)\n",
    "        qs.sort(key=functools.cmp_to_key(cmp))\n",
    "        # print(qs)\n",
    "\n",
    "        n = len(qs)\n",
    "        cnt = 0\n",
    "        for i in range(1, n):\n",
    "            a, b = qs[i - 1]\n",
    "            c, d = qs[i]\n",
    "            if b - a == d - c:\n",
    "                while a <= b:\n",
    "                    if nums[a] != nums[c]:\n",
    "                        break\n",
    "                    a += 1; c += 1\n",
    "                else:\n",
    "                    cnt += 1\n",
    "        return n - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        sets = set()\n",
    "        for n in nums:\n",
    "            if n % p == 0:\n",
    "                sets.add(n)\n",
    "        j = 0\n",
    "        cnt = 0\n",
    "        res = 0\n",
    "        combs = set()\n",
    "        mask = 0xFFFFFFFFFFFFFFF\n",
    "        prime = 211\n",
    "        for i in range(len(nums)):\n",
    "            cur = 0\n",
    "            # max of j is len(nums)\n",
    "            while cnt <= k and j < len(nums):\n",
    "                if nums[j] in sets:\n",
    "                    if cnt == k:\n",
    "                        break\n",
    "                    cnt += 1\n",
    "                j += 1\n",
    "            print(j)\n",
    "            # from i to j, exclusively\n",
    "            for m in range(i, j):\n",
    "                cur = (cur * prime + nums[m]) & mask\n",
    "                # print(\"cur:\", cur)\n",
    "                if cur not in combs:\n",
    "                    res += 1\n",
    "                    combs.add(cur)\n",
    "            if nums[i] in sets:\n",
    "                cnt -= 1\n",
    "            print(\"cnt:\", cnt)\n",
    "            # print(res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate([int(num%p == 0) for num in nums], initial=0))\n",
    "        p = [random.randint(26, 100), random.randint(26, 100)]\n",
    "        mod = [random.randint(10 ** 9 + 7, 2 ** 31 - 1), random.randint(10 ** 9 + 7, 2 ** 31 - 1)]\n",
    "        ans = set()\n",
    "        for i in range(n):\n",
    "            lst = [0, 0]\n",
    "            for j in range(i, n):\n",
    "                if pre[j+1] - pre[i] <= k:\n",
    "                    for x in range(2):\n",
    "                        lst[x] = (lst[x]*p[x]+nums[j]) % mod[x]\n",
    "                    ans.add((j-i+1,) + tuple(lst))\n",
    "                else:\n",
    "                    break\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "\n",
    "        n = len(nums)\n",
    "        pre = list(accumulate([int(num%p == 0) for num in nums], initial=0))\n",
    "        p = [random.randint(26, 100), random.randint(26, 100)]\n",
    "        mod = [random.randint(10 ** 9 + 7, 2 ** 31 - 1), random.randint(10 ** 9 + 7, 2 ** 31 - 1)]\n",
    "        ans = set()\n",
    "        for i in range(n):\n",
    "            lst = [0, 0]\n",
    "            for j in range(i, n):\n",
    "                if pre[j+1] - pre[i] <= k:\n",
    "                    for x in range(2):\n",
    "                        lst[x] = (lst[x]*p[x]+nums[j]) % mod[x]\n",
    "                    ans.add(tuple(lst))\n",
    "                else:\n",
    "                    break\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        is_exact_division = []\n",
    "        for num in nums:\n",
    "            is_exact_division.append(num % p == 0)\n",
    "        cache = {}\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i + 1, len(nums) + 1):\n",
    "                if sum(is_exact_division[i: j]) <= k and '_'.join(map(str, nums[i:j])) not in cache.keys():\n",
    "                    cache['_'.join(map(str, nums[i: j]))] = 1\n",
    "        return len(cache)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s = [str(num) for num in nums]\n",
    "        result = 0\n",
    "        book = set()\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(nums[j] % p == 0):\n",
    "                    cnt += 1\n",
    "                if(cnt > k):\n",
    "                    break\n",
    "                ts = '+'.join(s[j:i+1])\n",
    "                if(ts not in book):\n",
    "                    book.add(ts)\n",
    "                    result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s = [str(num) for num in nums]\n",
    "        result = 0\n",
    "        book = set()\n",
    "        n = len(s)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i,-1,-1):\n",
    "                if(nums[j] % p == 0):\n",
    "                    cnt += 1\n",
    "                if(cnt > k):\n",
    "                    break\n",
    "                ts = '+'.join(s[j:i+1])\n",
    "                if(ts not in book):\n",
    "                    book.add(ts)\n",
    "                    result += 1\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        can = []\n",
    "        for n in nums:\n",
    "            if n % p == 0:\n",
    "                can.append(1)\n",
    "            else:\n",
    "                can.append(0)\n",
    "        prefix = [0]\n",
    "        for c in can:\n",
    "            prefix.append(prefix[-1] + c)\n",
    "        res = set()\n",
    "        # print(prefix)\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i, len(nums)):\n",
    "                if prefix[j+1] - prefix[i] <= k:\n",
    "                    res.add(\",\".join([str(x) for x in nums[i:j+1]]))\n",
    "                    # print(len(res))\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        arr = [0 if i % p else 1 for i in nums]\n",
    "        n = len(nums)\n",
    "        prefix = [0] * n\n",
    "        prefix[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + arr[i]\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if arr[i]:\n",
    "                    if prefix[j] - prefix[i] <= k-1:\n",
    "                        res.add(str(nums[i:j + 1]))\n",
    "                else:\n",
    "                    if prefix[j] - prefix[i] <= k:\n",
    "                        res.add(str(nums[i:j + 1]))\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        arr = [0 if i % p else 1 for i in nums]\n",
    "        n = len(nums)\n",
    "        prefix = [0] * n\n",
    "        prefix[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + arr[i]\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if arr[i]:\n",
    "                    if prefix[j] - prefix[i] <= k-1:\n",
    "                        res.add(str(nums[i:j + 1]))\n",
    "                else:\n",
    "                    if prefix[j] - prefix[i] <= k:\n",
    "                        res.add(str(nums[i:j + 1]))\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        arr = []\n",
    "        for i in nums:\n",
    "            if i % p:\n",
    "                arr.append(0)\n",
    "            else:\n",
    "                arr.append(1)\n",
    "        n = len(nums)\n",
    "        prefix = [0] * n\n",
    "        prefix[0] = arr[0]\n",
    "        for i in range(1, n):\n",
    "            prefix[i] = prefix[i - 1] + arr[i]\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                if arr[i]:\n",
    "                    if prefix[j] - prefix[i] <= k-1:\n",
    "                        res.add(str(nums[i:j + 1]))\n",
    "                else:\n",
    "                    if prefix[j] - prefix[i] <= k:\n",
    "                        res.add(str(nums[i:j + 1]))\n",
    "        return len(res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        lens = len(nums)\n",
    "        res = []\n",
    "        total = 0\n",
    "        for i in range(1, lens + 1):\n",
    "            iters = self.combination(nums, i)\n",
    "            for item in iters:\n",
    "                if len(list(filter(lambda x: x % p == 0, item))) <= k:\n",
    "                    res.append(item)\n",
    "                    total += 1\n",
    "        return total\n",
    "\n",
    "    def combination(self, nums, size):\n",
    "        res = []\n",
    "        for i in range(len(nums) - size + 1):\n",
    "            subNums = nums[i:i + size]\n",
    "            if subNums not in res:\n",
    "                res.append(subNums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        valid = [num%p==0 for num in nums]\n",
    "        pre_sum = list(accumulate(valid, initial=0))\n",
    "        vis = set()\n",
    "        n = len(nums)\n",
    "        for length in range(1, n+1):\n",
    "            for left in range(n-length+1):\n",
    "                if pre_sum[left+length]-pre_sum[left]<=k:\n",
    "                    vis.add(tuple(nums[left:left+length]))\n",
    "        return len(vis)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        f = [0] * (n+1)\n",
    "        for i in range(n):\n",
    "            f[i+1] = f[i] + int(nums[i] % p == 0) \n",
    "        def calc(l, r):\n",
    "            return f[r+1] - f[l]\n",
    "        \n",
    "        ans = set()\n",
    "        for l in range(1, n+1):\n",
    "            for i in range(n-l+1):\n",
    "                j = i + l -1\n",
    "                if calc(i, j) <= k:\n",
    "                    ans.add(tuple(nums[i:j+1]))\n",
    "        return len(ans) "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n=len(nums)\n",
    "        trans=[]\n",
    "        arrs=set()\n",
    "        for i in range(n):\n",
    "            if nums[i]%p==0:\n",
    "                trans.append(1)\n",
    "            else:\n",
    "                trans.append(0)\n",
    "        presum=[0]\n",
    "        for p in range(n):\n",
    "            presum.append(sum(trans[:(p+1)]))\n",
    "        for j in range(1,n+1):\n",
    "            for u in range(n-j+1):\n",
    "                #从k到k+j\n",
    "                if presum[u+j]-presum[u]<=k:\n",
    "                    arrs.add(tuple(nums[u:u+j]))\n",
    "        arrs.add(tuple)\n",
    "        return len(arrs)-1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n=len(nums)\n",
    "        trans=[]\n",
    "        arrs=set()\n",
    "        for i in range(n):\n",
    "            if nums[i]%p==0:\n",
    "                trans.append(1)\n",
    "            else:\n",
    "                trans.append(0)\n",
    "        presum=[0]\n",
    "        for p in range(n):\n",
    "            presum.append(sum(trans[:(p+1)]))\n",
    "        for j in range(1,n+1):\n",
    "            for u in range(n-j+1):\n",
    "                #从k到k+j\n",
    "                if presum[u+j]-presum[u]<=k:\n",
    "                    arrs.add(tuple(nums[u:u+j]))\n",
    "        return len(arrs)\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        vnum = 0\n",
    "        n =len(nums)\n",
    "        setA = set()\n",
    "        l,r = 0,0\n",
    "        while r<n:\n",
    "            if nums[r]%p == 0:\n",
    "                vnum += 1\n",
    "            while vnum>k:\n",
    "                if nums[l]%p==0:\n",
    "                    vnum -= 1\n",
    "                l+=1\n",
    "            for i in range(l,r+1):\n",
    "                setA.add(tuple(nums[i:r+1]))\n",
    "            r+=1\n",
    "        return len(setA)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        # 统计有多少个满足条件的\n",
    "        res = 0\n",
    "        # 做一个去重的操作\n",
    "        hashset = set()\n",
    "\n",
    "        for index in range(len(nums)):\n",
    "            left = index\n",
    "            # 代表窗口内多少元素可以被p整除，其限制是k \n",
    "            count = 0\n",
    "            for right in range(left,len(nums)):\n",
    "                if nums[right] % p == 0:\n",
    "                    count += 1\n",
    "                while count > k:\n",
    "                    if nums[left] % p == 0:\n",
    "                        count -= 1\n",
    "                    left += 1\n",
    "                t = tuple(nums[left:right+1]) \n",
    "                if t not in hashset:\n",
    "                    res += 1\n",
    "                    hashset.add(t)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        lstSet = set()\n",
    "        n = len(nums)\n",
    "        div = [False]*n\n",
    "        for i in range(n):\n",
    "            div[i] = (nums[i] % p ==0)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            arr = []\n",
    "            for j in range(i,n):\n",
    "                if div[j]:\n",
    "                    cnt+=1\n",
    "                    if cnt>k:\n",
    "                        break\n",
    "                arr.append(nums[j])\n",
    "                lstSet.add(tuple(arr))\n",
    "        \n",
    "        return len(lstSet)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        vnum = 0\n",
    "        n =len(nums)\n",
    "        setA = set()\n",
    "        l,r = 0,0\n",
    "        while r<n:\n",
    "            if nums[r]%p == 0:\n",
    "                vnum += 1\n",
    "            while vnum>k:\n",
    "                if nums[l]%p==0:\n",
    "                    vnum -= 1\n",
    "                l+=1\n",
    "            for i in range(l,r+1):\n",
    "                setA.add(tuple(nums[i:r+1]))\n",
    "            r+=1\n",
    "        return len(setA)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        ans = 0\n",
    "        valid_sub = set([])\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                num = nums[j]\n",
    "                if num % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                valid_sub.add(tuple(nums[i:j + 1]))\n",
    "        \n",
    "        return  len(valid_sub)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s = set()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i:j + 1]))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i:j+1]))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s = set()\n",
    "        for i in range(len(nums)):\n",
    "            count = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                if nums[j] % p == 0:\n",
    "                    count += 1\n",
    "                if count > k:\n",
    "                    break\n",
    "                s.add(tuple(nums[i:j+1]))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        '''\n",
    "            滑动窗口，对于以每一个元素为右端点的最大滑动窗口，将可能的区间添加到set中去重\n",
    "        '''\n",
    "        res = set()\n",
    "        i = 0\n",
    "        cur_k = 0\n",
    "        for j in range(len(nums)):\n",
    "            cur_k += 1 if nums[j] % p == 0 else 0\n",
    "            while cur_k > k:\n",
    "                cur_k -= 1 if nums[i] % p == 0 else 0\n",
    "                i += 1\n",
    "            for t in range(i, j+1):\n",
    "                res.add(tuple(nums[t:j+1]))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i: j + 1]))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i: j + 1]))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        res = set()\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                if cnt > k:\n",
    "                    if nums[i] % p == 0:\n",
    "                        cnt -= 1\n",
    "                    break\n",
    "                res.add(tuple(nums[i:j + 1]))\n",
    "        return len(res)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s,n=set(),len(nums)\n",
    "        for i in range(n):\n",
    "            cnt=0\n",
    "            for j in range(i,n):\n",
    "                if nums[j]%p==0:\n",
    "                    cnt+=1\n",
    "                    if cnt>k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i:j+1]))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        i,j=0,0\n",
    "        c=0\n",
    "        n=len(nums)\n",
    "        s=set()\n",
    "        while j<n:\n",
    "            if nums[j]%p==0:\n",
    "                c+=1\n",
    "            #print(i,j,c)\n",
    "            while c>k and i<j:\n",
    "                #print(c,k,i,j)\n",
    "                if nums[i]%p==0:\n",
    "                    c-=1\n",
    "                i+=1\n",
    "            for kk in range(i,j+1):\n",
    "                s.add(tuple(nums[kk:j+1]))\n",
    "            j+=1\n",
    "       #print(s)\n",
    "        return len(list(s))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        ans = set()\n",
    "        left = 0\n",
    "        cnt = 0\n",
    "        for right in range(len(nums)):\n",
    "            if nums[right] % p == 0:\n",
    "                cnt += 1\n",
    "            while cnt > k:\n",
    "                if nums[left] % p == 0:\n",
    "                    cnt -= 1\n",
    "                left += 1\n",
    "            for i in range(left, right + 1):\n",
    "                ans.add(tuple(nums[i:right + 1]))\n",
    "        return len(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        # 记录符合条件的子数组\n",
    "        record = set()\n",
    "        for i in range(len(nums)):\n",
    "            # 记录可以被整除的元素个数\n",
    "            count = 0\n",
    "            for j in range(i, len(nums)):\n",
    "                # 元素可以被整除，个数加1，如果个数超过最大限制，退出循环\n",
    "                if nums[j] % p == 0:\n",
    "                    count += 1\n",
    "                    if count > k:\n",
    "                        break\n",
    "                record.add(tuple(nums[i:j+1]))\n",
    "        return len(record)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        vis = set()\n",
    "        ans = 0\n",
    "        for i in range(n):\n",
    "            c = 0\n",
    "            for j in range(i, n):\n",
    "                c += nums[j] % p == 0\n",
    "                tmp = tuple(nums[i:j + 1])\n",
    "                if c <= k and tmp not in vis:\n",
    "                    ans += 1\n",
    "                    vis.add(tmp)\n",
    "                if c > k:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        n = len(nums)\n",
    "        s = set()\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                cnt += nums[j] % p == 0\n",
    "                if cnt > k:\n",
    "                    break\n",
    "                s.add(tuple(nums[i: j + 1]))\n",
    "        return len(s)\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        visit = set()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                visit.add(tuple(nums[i: j + 1]))\n",
    "        return len(visit)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i: j + 1]))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        # 不同子数组的定义\n",
    "        # 子数组长度不同\n",
    "        # 长度相同的话，各个位置的值不能全部相同\n",
    "        # 简单想法，枚举出所有的子数组，然后去重，去重完成之后在判断其中满足要求的子数组有多少个\n",
    "        n = len(nums)\n",
    "        seen = set()\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i,n):\n",
    "                if nums[j]%p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                seen.add(tuple(nums[i:j+1]))\n",
    "        return len(seen)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        # is_exact_division = []\n",
    "        # for num in nums:\n",
    "        #     is_exact_division.append(num % p == 0)\n",
    "        # cache = {}\n",
    "        # for i in range(len(nums)):\n",
    "        #     for j in range(i + 1, len(nums) + 1):\n",
    "        #         if sum(is_exact_division[i: j]) <= k and '_'.join(map(str, nums[i:j])) not in cache.keys():\n",
    "        #             cache['_'.join(map(str, nums[i: j]))] = 1\n",
    "        # return len(cache)\n",
    "\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i: j + 1]))\n",
    "        return len(s)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        res=set()\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            for j in range(i,len(nums)):\n",
    "                if j-i+1<=k:\n",
    "                    res.add(tuple(nums[i:j+1]))\n",
    "                else:\n",
    "                    ant=0\n",
    "                    for num in nums[i:j+1]:\n",
    "                        if num%p==0:\n",
    "                            ant+=1\n",
    "                            if ant>k:\n",
    "                                break\n",
    "                    if ant>k:\n",
    "                        break\n",
    "                    else:\n",
    "                        res.add(tuple(nums[i:j+1]))\n",
    "        \n",
    "        return len(res)\n",
    "\n",
    "\n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        st = set()  # 存储tuple，去重\n",
    "        l = 0\n",
    "        cnt = 0\n",
    "        for r, x in enumerate(nums):\n",
    "            cnt += int(x % p == 0)\n",
    "            while cnt > k:\n",
    "                cnt -= int(nums[l] % p == 0)\n",
    "                l += 1\n",
    "            for j in range(l, r + 1):\n",
    "                st.add(tuple(nums[j: r + 1]))\n",
    "        return len(st)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s = set()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                if cnt > k:\n",
    "                    break\n",
    "                s.add(tuple(nums[i: j+1]))\n",
    "\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k: break\n",
    "                s.add(tuple(nums[i:j+1]))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        nums_1 = [int(num % p == 0) for num in nums]\n",
    "        for i in range(1, len(nums_1)):\n",
    "            nums_1[i] += nums_1[i-1]\n",
    "        nums_1 = [0] + nums_1\n",
    "        temp = set()\n",
    "        ans = 0\n",
    "        for i in range(len(nums_1)-1):\n",
    "            for j in range(i + 1, len(nums_1)):\n",
    "                if nums_1[j] - nums_1[i] <= k:\n",
    "                    if tuple(nums[i:j]) not in temp:\n",
    "                        ans += 1\n",
    "                        temp.add(tuple(nums[i:j]))\n",
    "                else:\n",
    "                    break\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        se1, lens = set(), len(nums)\n",
    "        for i in range(lens):\n",
    "            cnt = 0\n",
    "            for j in range(i,lens):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                if cnt > k:\n",
    "                    break\n",
    "                se1.add(tuple(nums[i:j+1]))\n",
    "        return len(se1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        s, n = set(), len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i: j + 1]))\n",
    "        return len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        # 不同子数组的定义\n",
    "        # 子数组长度不同\n",
    "        # 长度相同的话，各个位置的值不能全部相同\n",
    "        # 简单想法，枚举出所有的子数组，然后去重，去重完成之后在判断其中满足要求的子数组有多少个\n",
    "        s = set()\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            cnt = 0\n",
    "            for j in range(i,n):\n",
    "                if nums[j]%p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                s.add(tuple(nums[i:j+1]))\n",
    "        return len(s)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countDistinct(self, nums: List[int], k: int, p: int) -> int:\n",
    "        arrs = set()   # 不同的（序列化后）子数组\n",
    "        n = len(nums)\n",
    "        # 枚举左右边界\n",
    "        for i in range(n):\n",
    "            cnt = 0   # 当前被 p 整除的元素个数\n",
    "            arr = []   # 当前子数组\n",
    "            for j in range(i, n):\n",
    "                if nums[j] % p == 0:\n",
    "                    cnt += 1\n",
    "                    if cnt > k:\n",
    "                        break\n",
    "                arr.append(nums[j])\n",
    "                # 序列化后放入哈希集合\n",
    "                arrs.add(tuple(arr))\n",
    "        return len(arrs)"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
